import java.util.HashSet;
import java.util.Iterator;

public class No056 {
    /**
     * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
     */
    //num1,num2分别为长度为1的数组。传出参数
    //将num1[0],num2[0]设置为返回结果
    public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2) {
        if (array.length < 2) return;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (set.contains(array[i])) {
                set.remove(array[i]);
            } else {
                set.add(array[i]);
            }
        }
        Iterator<Integer> iterator = set.iterator();
        num1[0] = iterator.next();
        num2[0] = iterator.next();
    }

    // 两个相同的数字异或为0

    public void FindNumsAppearOnce2(int[] array, int[] num1, int[] num2) {
        if (array.length < 2) return;
        int resultExclusiveOR = 0;
        for (int item : array) {
            resultExclusiveOR ^= item;          // 异或结果肯定不为0
        }
        int index = 1;
        // 第index位为1
        while ((resultExclusiveOR & index) == 0) {
            index = index << 1;
        }
        int result1 = 0, result2 = 0;
        for (int value : array) {
            // 第index位为0的数
            if ((index & value) == 0) {
                result1 ^= value;       //剩下不重复的数
            }
            // 第index位为1的数
            else {
                result2 ^= value;      //剩下不重复的数
            }
        }
        num1[0] = result1;
        num2[0] = result2;
    }

    /**
     * 题目二：数组中唯一只出现一次的数字。
     * 在一个数组中除一个数字只出现一次之外，其他数字都出现了三次。
     * 请找出那个只出现一次的数字。
     */
    public int FindNumberAppearingOnce(int[] array) {
        if (array.length == 0) return -1;
        int[] bitSum = new int[32];
        for (int i = 0; i < array.length; i++) {
            int bitMask = 1;
            for (int j = 31; j >= 0; j--) {
                int bit = array[i] & bitMask;
                if (bit != 0) {
                    bitSum[j]++;
                }
                bitMask = bitMask << 1;
            }
        }
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = result << 1;
            result += bitSum[i] % 3;
        }
        return result;
    }
}
